package leetcode.code0664;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：18 ms, 在所有 Java 提交中击败了36.90%的用户
 *
 * 内存消耗：38 MB, 在所有 Java 提交中击败了93.73%的用户
 *
 * 通过测试用例：200 / 200
 */
public class Solution5 implements IDebug {

	public int strangePrinter(String s) {
		int len = s.length();
		char[] cs = s.toCharArray();
		int p = 0;
		int i = 0;
		while (i < len) {// 快6ms
			if (cs[i] == cs[p]) {
				i++;
			} else {
				cs[++p] = cs[i++];
			}
		}
		Integer[][] dp = new Integer[len][len];
		for (int l = p; l >= 0; l--) {
			dp[l][l] = 1;
			for (int r = l + 1; r <= p; r++) {
				int ans = Integer.MAX_VALUE;
				for (int k = l; k < r; k++) {
					int ansk = dp[l][k] + dp[k + 1][r];
					if (cs[l] == cs[k + 1]) {
						ansk -= 1;
					}
					ans = Math.min(ansk, ans);
				}
				dp[l][r] = ans;
			}
		}
		return dp[0][p];
	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.strangePrinter("aaabbb"));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(6, this.strangePrinter("sdfasdf"));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(2, this.strangePrinter("aba"));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution5 so = new Solution5();
		so.debug1();
		so.debug2();
		so.debug3();
//		D.debug14(so);

	}

}
